;================================================================


check_equal proc far   
; 函数 检查两段数据是否完全相等
; 参数：ax 要检查数据的长度  ds:si es:di 两段数据所在地址
; 返回: ax = 1 相等  ax =0 不相等
    push bx
    push cx
    push dx

    mov cx,ax
    xor bx,bx
check_equal_cycle:
    mov al,ds:[si+bx]
    mov dl,es:[di+bx]
    cmp al,dl
    jnz check_equal_false
    inc bx
    loop check_equal_cycle
    jmp check_equal_true


check_equal_true:
    mov ax,1h
    pop dx
    pop cx
    pop bx
    retf


check_equal_false:
    mov ax,0h
    pop dx
    pop cx
    pop bx
    retf
check_equal endp

Kmp proc far
; KMP算法比较两字符串是否相等
; 参数: ds:si  es:di  两字符串位置(预留80字节空间 子字符串长度要小于40,next数组保存在es:[di+40]上)  ax 最大匹配字符串长度


    push bx
    push cx
    push dx

    push ds
    push si
    push es
    push di

    push ax ; ss:[bp+2] 最大匹配字符串长度

    mov cx,ds
    mov dx,si
    mov ax,es
    mov ds,ax
    mov si,di   ; ds:si <= es:di

    call far ptr build_next

    mov ds,cx
    mov si,dx

    push bp
    mov bp,sp

    xor ax,ax
    push ax  ; ss:[bp-2]    i = 0 主串指针   ds:[si+bx]
    push ax  ; ss:[bp-4]    j = 0 子串指针   es:[di+bx]

    xor ah,ah 
    xor bh,bh
    xor ch,ch
    xor dh,dh

Kmp_loop:
    ; i = len(str) false
    mov bl,ss:[bp-2]
    mov al,ds:[si+bx]
    cmp al,0h
    jz Kmp_return_false
    mov al,ss:[bp-2]
    mov bl,ss:[bp+2]
    cmp al,bl   ; j >= max_len 结束
    jnl Kmp_return_false

    mov bl,ss:[bp-2]
    mov cl,ds:[si+bx]
    mov bl,ss:[bp-4]
    mov dl,es:[di+bx]
    cmp cl,dl
    jnz Kmp_loop_continue1

    mov al,ss:[bp-2]
    inc al
    mov ss:[bp-2],al   ;i+=1

    mov al,ss:[bp-4]
    inc al
    mov ss:[bp-4],al   ;j+=1

    jmp Kmp_loop_continue3

Kmp_loop_continue1:
    mov bl,ss:[bp-4]
    cmp bl,0
    jle Kmp_loop_continue2

    ; j = next[j-1]


    mov bl,ss:[bp-4]
    dec bl
    mov al,es:[di+bx+28h]  ;从next表中取数据,写入j
    mov ss:[bp-4],al
    jmp Kmp_loop_continue3

Kmp_loop_continue2:
    mov al,ss:[bp-2]
    inc al
    mov ss:[bp-2],al   ; i+=1
    ; jmp Kmp_loop_continue3


Kmp_loop_continue3:
    ; j =len(patt) true
    mov bl,ss:[bp-4]
    mov ax,es:[di+bx]
    cmp al,0h
    jz Kmp_return_true
    jmp Kmp_loop



Kmp_return_false:
    add sp,4h
    pop bp
    mov ax,0h
    add sp,2h  

    pop di
    pop ax
    mov es,ax
    pop si
    pop ax
    mov ds,ax

    pop dx
    pop cx
    pop bx

    retf

Kmp_return_true:
    add sp,4h
    pop bp
    mov ax,1h
    add sp,2h  

    pop di
    pop bx
    mov es,bx
    pop si
    pop bx
    mov ds,bx

    pop dx
    pop cx
    pop bx

    retf





Kmp endp


build_next proc far
; 生成next数组
; 参数: ds:si
; 结果保存在 ds:[si+28h]中
    push ax
    push bx
    push cx
    push dx

    push ds
    push si

    push es
    push di







    push bp
    mov bp,sp
    mov ax,1h
    push ax   ; ss:[bp-2]     i = 0  （由于next数组的首）
    xor ax,ax
    push ax   ; ss:[bp-4]     当前共同前后缀长度 prelen= 0
    mov ax,1h    
    push ax   ; ss:[bp-6]     next数组的长度(从1开始) len = 1
 


    mov ax,ds
    mov es,ax
    mov di,si
    add di,28h    ; es:di 为next数组地址


    xor ax,ax
    mov es:[di],al    ; next[0] = 0

    ; mov cx,0h       
    ; mov dx,0h      
    xor ah,ah 
    xor bh,bh
    xor ch,ch
    xor dh,dh

build_next_loop:

    mov bl,ss:[bp-2]

    mov al,ds:[si+bx]
    cmp al,00h     ; 取到字符串末尾，结束循环
    jz build_next_done

    mov bl,ss:[bp-2]
    mov cl,ds:[si+bx]
    mov bl,ss:[bp-4]
    mov dl,ds:[si+bx]

    cmp cl,dl   ; str[prelen] = str[i]
    jnz build_next_continue1

    mov al,ss:[bp-4]  
    inc al
    mov ss:[bp-4],al   ;prelen+=1


    mov bl,ss:[bp-6]
    mov es:[di+bx],al
    inc bl
    mov ss:[bp-6],bl   ;len+=1

    mov al,ss:[bp-2]  
    inc al
    mov ss:[bp-2],al   ;i+=1

    jmp build_next_loop

build_next_continue1:
    mov al,ss:[bp-4]
    cmp al,00h
    jnz build_next_continue2

    mov bl,ss:[bp-6]
    mov es:[di+bx],al
    inc bl
    mov ss:[bp-6],bl   ;len+=1

    mov al,ss:[bp-2]  
    inc al
    mov ss:[bp-2],al   ;i+=1



    jmp build_next_loop

build_next_continue2:

    mov bx,ss:[bp-4]
    dec bl
    mov al,es:[di+bx]
    mov ss:[bp-4],ax


    jmp build_next_loop






build_next_done:

    add sp,6h
    pop bp

    pop di
    pop ax
    mov es,ax

    pop si
    pop ax
    mov ds,ax

    pop dx
    pop cx
    pop bx
    pop ax

    ret

build_next endp
;================================================================

Get_pointers  proc far  
; 函数：从pointers段获取目标地址
; 参数：ax: 要查询第几个地址 
; 返回：ax: 目标偏移地址 若查询的地址位置大于总地址数，返回ax = BADh

    

    push dx
    push ds
    push si
    push bx


    mov bx,ss:[bp+16h]
    cmp ax,bx
    jnb Get_pointers_error



    mov bl,2h
    mul bl
    mov bx,ax
    mov ax,pointers
    mov ds,ax
    lea si,pointers_start

    mov dx,ds:[si+bx]

    pop bx
    pop si
    pop ax
    mov ds,ax

    mov ax,dx
    pop dx


    retf
Get_pointers_error:
    pop bx
    pop si
    pop ax
    mov ds,ax

    mov ax,0BADh
    pop dx
    



    retf
Get_pointers endp
